package test3;

import java.util.Scanner;

public class Solution3 {
    public static void main(String[] args) {// 预排序思想
        Scanner sc = new Scanner(System.in);
        System.out.println("请输入数组的元素个数：");
        int num = sc.nextInt();
        int[] arr = new int[num];
        System.out.println("请输入数组：");
        for (int i = 0; i < num; i++) {
            arr[i] = sc.nextInt();
        }
        System.out.println("请输入所求的和：");
        int sum = sc.nextInt();
        //快速排序
        quickSort(arr, 0, num - 1);
        int a = 0, b = 0, target = 0;
        //二分查找sum - a在不在数组中
        for (int i = 0; i < num; i++){
            target = sum - arr[i];
            b = binarySearch(arr, target);
            a = i;
            if (b != -1) break;
        }
        System.out.println(arr[a] + " + " + arr[b] + " 的数字之和为 " + sum);
    }

    private static int binarySearch(int[] arr, int target) {
        int left = 0;
        int right = arr.length - 1;
        while (left <= right){
            int mid = left + (right - left) / 2;
            if (arr[mid] > target){
                right = mid - 1;//查找元素在左边，将右边界设置为mid-1
            }else if (arr[mid] < target){
                left = mid + 1;//查找元素在右边，将左边边界设置为mid+1
            }else {
                return mid;
            }
        }
        return -1;
    }

    private static void quickSort(int[] arr, int L, int R) {
        if (L >= R) return;
        int left = L, right = R;
        int pivot = arr[left];
        while (left < right){
            while (left < right && arr[right] >= pivot){//如果右边的元素比选定元素大，则指针向左移动
                right--;
            }
            //此时的情况是右边的元素小于选定元素，则被左边元素替换
            if(left < right){
                arr[left] = arr[right];
            }
            while (left < right && arr[left] <= pivot){
                left++;
            }
            if (left < right){
                arr[right] = arr[left];
            }
            //左右相遇则将选定元素放入
            if (left >= right){
                arr[left] = pivot;
            }
        }
        quickSort(arr, L, right - 1);
        quickSort(arr, right + 1, R);
    }
}
